#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 704. 二分查找.py
@time: 2022/1/11 20:56
@desc: https://leetcode-cn.com/problems/binary-search/
> 给定一个n个元素有序的（升序）整型数组nums 和一个目标值target ，写一个函数搜索nums中的 target，如果目标值存在返回下标，否则返回 -1。

'''


class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums: return -1
        n = len(nums)
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

# 递归
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        def bs(nums, left ,right):
            if left>right:
                return -1
            mid = (left + right)//2
            if target==nums[mid]: return mid
            if target>nums[mid]: return bs(nums, mid+1, right)
            else: return bs(nums, left, mid-1)

        return bs(nums, 0, len(nums)-1)